package combinations;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class SuperSet {

	public static void main(String[] args) {
		List<int[]> sets = getSuperSetMinusEmptySet(5);
		for(int[] set : sets){
			System.out.println(":" + utils.Util.printIntArray(set) );
		}
	}
	
	public static List<int[]> getSuperSetMinusEmptySet(int numElements){
		List<int[]> result = getSuperSet(numElements);
		result.remove(0);
		return result;
	}
	
	public static List<int[]> getSuperSet(int numElements){
		//obtain superset through bit addition
		//an element has a 1 if it is present
		//and a 0 if it is absent
		List<int[]> result = new ArrayList<int[]>();
		int[] currentSet = new int[numElements];
		boolean overflow = false;
		while(!overflow){
			int[] copy = Arrays.copyOf(currentSet, currentSet.length);
			result.add(copy);
			for(int i = numElements - 1; i >= 0; i--){
				if(currentSet[i] == 0){
					//no need for carry-over;  add 1 and break
					currentSet[i] = 1; break;
				} else // currentSet[i] == 1
					//if at highest bit, carry won't work
					if(i == 0){
						overflow = true; break;
					}
					//add 1 and carry to next bit
					currentSet[i] = 0;
			}
		}
		return result;
	}
	
	
	
}
